package string;

/**
 * 用来计算字符串的最长回文字符串的一个类
 * 计算总共有四种方式，暴力破解、中间扩散、动态规划和 Manacher
 * 此处仅提供后两种
 * @author  HuWLin
 *
 * */

public class LongestPalindrome {
    /*
    * 动态规划计算
    * 时间复杂度为O(n^2)
    * @param s
    *        传入字符串
    * @return
    *        返回最长回文字符串
    * */
    public static String dynamicProgramming(String s){
        //len计算字符串的长度
        int len = s.length();
        //MaxLen最小唯1，因为一个字符一定是回文字符串，start为字符串开始的下标
        int MaxLen = 1,start = 0;
        //dp统计在i和j位置两个字符串是否相等
        boolean[][] dp = new boolean[len][len];
        //一个字符串肯定是回文字符串
        for(int i = 0;i < len;i ++){
            dp[i][i] = true;
        }
        char[] sArr = s.toCharArray();
        for(int j = 1;j < len;j ++){
            for(int i = 0;i < j;i ++){
                int l = j - i + 1;
                if(sArr[i] != sArr[j]){
                    dp[i][j] = false;
                }else {
                    //如果当前字符串长度小于等于3就直接返回true,否则去判断各往里一位是否为true
                    dp[i][j] = l <= 3 || dp[i + 1][j - 1];
                }
                if(dp[i][j] && l > MaxLen){
                    MaxLen = l;
                    start = i;
                }
            }
        }
        return s.substring(start,start + MaxLen);
    }

    /*
    * Manacher算法
    * 时间复杂度为O(n)
    * @param s
    *        传入字符串
    *
    * @return
    *        返回最长回文字符串
    * */
    public static String manacher(String s){
        if(s.length() < 2){
            return s;
        }
        //单线程使用StringBuilder最快
        StringBuilder sb = new StringBuilder("#");
        int MaxLen = 1,start = 0;
        for(int i = 0;i < s.length();i ++){
            sb.append(s.charAt(i));
            sb.append("#");
        }
        int newLen = sb.length();
        String newS = sb.toString();
        //lastCenter用来记录之前最长的回文数的中心点的下表，right为此字符串的最右边加一的下标
        int lastCenter = -1,right = -1;
        int[] p = new int[newLen];
        for(int i = 0;i < newLen;i ++){
            /*
             * 这句话比较难以理解，可以多看点资料，当前i点与之前最长的回文数中心存在对称点j，
             * 此时只要拿到之前的p[j]即可减少计算，若之前的j + p[j] > lastCenter时，则只能使用到right - i
             * 若要学习可以去找更好的资料
             *
             */
            p[i] = right > i ?Math.min(p[lastCenter * 2 - i],right - i):1;

            //此处就是一个中心扩散
            while(i - p[i] > -1 && i + p[i] < newLen){
                if(newS.charAt(i - p[i]) == newS.charAt(i + p[i])){
                    p[i] ++;
                }else {
                    break;
                }
            }

            //如果最新的最长回文字符串长度大于之前的则更新
            if(p[i] + i > right){
                right = p[i] + i;
                lastCenter = i;
            }
            //用于取到最长的回文字符串开始位置下表和长度，此处最长指的是转换后的字符串
            int nowLen = (i + p[i]) - (i - p[i]) - 1;
            if(nowLen > MaxLen){
                MaxLen = nowLen;
                start = i - p[i] + 1;
            }
        }
        //此处进行还原字符串的开始位置和长度
        start /= 2;
        MaxLen = (MaxLen - 1) / 2;
        return s.substring(start,start + MaxLen);
    }
}
